package find;

import java.util.Arrays;

public class MyKmp {

	public int kmp(String string, String pattern){
		if(pattern == null || pattern.length() <= 0){
			return 0;
		}
		if(string == null || string.length() <= 0){
			return 0;
		}
		int lengthPattern = pattern.length();
		int lengthString = string.length();
		
		
//		Arrays.sort(a)
		char[] chas = string.toCharArray();
		char[] find = pattern.toCharArray();
		int[] next = next(pattern);
		
		int count = 0;
		int k = 0;
		for (int i = 0; i < lengthString; i++) {
			if(chas[i] == find[k]){
				k++;
			}else{
				while(k > 0 && chas[i] != find[k]){
					k = next[k - 1];
				}
				if(chas[i] == find[k]){
					k++;
				}
			}
			if(k == lengthPattern){
				count++;
				k = next[k - 1];
			}
		}
		return count;
	}
	
	public int[] next(String pattern){
		if(pattern == null || pattern.length() <= 0){
			return new int[]{};
		}
		int length = pattern.length();
		
		char[] chas = pattern.toCharArray();
		int[] next = new int[length];
		next[0] = 0;
		
		int k = 0, index = 1;
		for (; index < length; index++) {
			if(chas[index] == chas[k]){
				//匹配的话
				k++;
				next[index] = next[index - 1] + 1;
			}else{
				//不匹配的话 ，我们移动k就行
				//这儿也是一个kmp的思想
				while(k > 0 && chas[index] != chas[k]){
					k = next[k - 1];
				}
				if(chas[index] == chas[k]){
					k++;
				}
				next[index] = k;
			}
		}
		return next;
	}
}
